import java.util.*;
/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 01
 * Time: 9:10
 */
//牛客 滑动窗口的最大值
public class Solution5 {
    //法一 优先级队列
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 1. 优先队列的每个元素都是二元组(num,index) : 大根堆（元素大小不同按元素大小排列，元素大小相同按下标进行排列）
        // num :   用来存入结果数组
        // index : 用来判断堆顶元素是否在窗口内
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] pair1,int[] pair2){
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0]:pair2[1] - pair1[1];//2-1建的是大根堆
            }
        });
        // 2. 优选队列初始化 : k个元素的堆
        for(int i = 0;i < k;i++){
            pq.offer(new int[]{nums[i],i});
        }
        // 3. 处理堆逻辑
        int[] res = new int[n - k + 1];         // 初始化结果数组长度 ：一共有 n - k + 1个窗口
        res[0] = pq.peek()[0];                  // 初始化res[0] ： 拿出目前堆顶的元素
        for(int i = k;i < n;i++){               // 向右移动滑动窗口
            pq.offer(new int[]{nums[i],i});     // 加入大根堆中
            while(pq.peek()[1] <= i - k){       // 将下标不在滑动窗口且在堆顶的元素都去掉
                pq.poll();
            }
            res[i - k + 1] = pq.peek()[0];      // 此时堆顶元素就是滑动窗口的最大值
        }
        return res;
    }


    //法二 双端队列 牛客官方推荐方法
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {//维护单调递减栈
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {//维护单调递减栈
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }


    //法三
    public ArrayList<Integer> maxInWindows1 (int[] num, int size) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if(size > num.length || size == 0) return arrayList;
        for (int i = 0; i <= num.length - size; i++) {
            int max = 0;
            for (int j = i; j < i + size; j++) {
                if(num[j] > max) {
                    max = num[j];
                }
            }
            arrayList.add(max);
        }
        return arrayList;
    }
    public ArrayList<Integer> maxInWindows2 (int[] num, int size) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if(size > num.length || size == 0) return arrayList;
        for (int i = 0; i <= num.length - size; i++) {
            arrayList.add(maxInWindowsF(num, size, i));
        }
        return arrayList;
    }
    public int maxInWindowsF(int[] num, int size, int i) {
        int max = 0;
        for (int j = i; j < i + size; j++) {
            if(num[j] > max) {
                max = num[j];
            }
        }
        return max;
    }
}
